package com.zhaopin.theswordreferstooffer;

import java.util.Stack;

/**
 * @author yin.peide
 * @date 2021-06-11 17:00
 * 面试题22：栈的压入，弹出序列
 */
public class Offer22 {

    public static void main(String[] args) {
        int[] pushed = {1, 2, 3, 4, 5};

        //属于弹出的序列
        int[] popped1 = {4, 5, 3, 2, 1};
        //不属于弹出的序列
        int[] popped2 = {4, 3, 5, 1, 2};

        System.out.println(validateStackSequences(pushed, popped1));

        System.out.println(validateStackSequences(pushed, popped2));


    }

    /**
     * 这题主要考察对栈的理解，栈是一种先进后出的数据结构，如果栈顶元素不出栈，那么栈顶元素下面的元素都是不能出栈的。
     *
     *
     * 一种解决方式就是把pushed数组的元素逐个压栈，当栈顶元素等于popped数组中第一个元素的时候，就让栈顶元素出栈，
     * 这个时候再用popped数组的第2个元素和栈顶元素比较，如果相同继续出栈……，最后判断栈是否为空即可，来看下代码
     * @param pushed
     * @param popped
     * @return
     */
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for (int val : pushed) {
            //pushed数组中的元素逐个压栈
            stack.push(val);
            while (!stack.empty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.empty();
    }
}
